<html>
 <head>
  <link href="./leetcode-problem.css" rel="stylesheet" type="text/css">
 </head>
 <body>
  <div class="question_difficulty">
   难度：Medium
  </div>
  <div>
   <h1 class="question_title">
    207. Course Schedule
   </h1>
   <p>
    There are a total of
    <i>
     n
    </i>
    courses you have to take, labeled from
    <code>
     0
    </code>
    to
    <code>
     n-1
    </code>
    .
   </p>
   <p>
    Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair:
    <code>
     [0,1]
    </code>
   </p>
   <p>
    Given the total number of courses and a list of prerequisite
    <b>
     pairs
    </b>
    , is it possible for you to finish all courses?
   </p>
   <p>
    <strong>
     Example 1:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> 2, [[1,0]] 
<strong>Output: </strong>true
<strong>Explanation:</strong>&nbsp;There are a total of 2 courses to take. 
&nbsp;            To take course 1 you should have finished course 0. So it is possible.</pre>
   <p>
    <strong>
     Example 2:
    </strong>
   </p>
   <pre>
<strong>Input:</strong> 2, [[1,0],[0,1]]
<strong>Output: </strong>false
<strong>Explanation:</strong>&nbsp;There are a total of 2 courses to take. 
&nbsp;            To take course 1 you should have finished course 0, and to take course 0 you should
&nbsp;            also have finished course 1. So it is impossible.
</pre>
   <p>
    <b>
     Note:
    </b>
   </p>
   <ol>
    <li>
     The input prerequisites is a graph represented by
     <b>
      a list of edges
     </b>
     , not adjacency matrices. Read more about
     <a href="https://www.khanacademy.org/computing/computer-science/algorithms/graph-representation/a/representing-graphs" target="_blank">
      how a graph is represented
     </a>
     .
    </li>
    <li>
     You may assume that there are no duplicate edges in the input prerequisites.
    </li>
   </ol>
  </div>
  <div>
   <h1 class="question_title">
    207. 课程表
   </h1>
   <p>
    现在你总共有
    <em>
     n
    </em>
    门课需要选，记为&nbsp;
    <code>
     0
    </code>
    &nbsp;到&nbsp;
    <code>
     n-1
    </code>
    。
   </p>
   <p>
    在选修某些课程之前需要一些先修课程。&nbsp;例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们:
    <code>
     [0,1]
    </code>
   </p>
   <p>
    给定课程总量以及它们的先决条件，判断是否可能完成所有课程的学习？
   </p>
   <p>
    <strong>
     示例 1:
    </strong>
   </p>
   <pre><strong>输入:</strong> 2, [[1,0]] 
<strong>输出: </strong>true
<strong>解释:</strong>&nbsp;总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。</pre>
   <p>
    <strong>
     示例 2:
    </strong>
   </p>
   <pre><strong>输入:</strong> 2, [[1,0],[0,1]]
<strong>输出: </strong>false
<strong>解释:</strong>&nbsp;总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。</pre>
   <p>
    <strong>
     说明:
    </strong>
   </p>
   <ol>
    <li>
     输入的先决条件是由
     <strong>
      边缘列表
     </strong>
     表示的图形，而不是邻接矩阵。详情请参见
     <a href="http://blog.csdn.net/woaidapaopao/article/details/51732947" target="_blank">
      图的表示法
     </a>
     。
    </li>
    <li>
     你可以假定输入的先决条件中没有重复的边。
    </li>
   </ol>
   <p>
    <strong>
     提示:
    </strong>
   </p>
   <ol>
    <li>
     这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
    </li>
    <li>
     <a href="https://www.coursera.org/specializations/algorithms" target="_blank">
      通过 DFS 进行拓扑排序
     </a>
     - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
    </li>
    <li>
     <p>
      拓扑排序也可以通过&nbsp;
      <a href="https://baike.baidu.com/item/%E5%AE%BD%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2/5224802?fr=aladdin&amp;fromid=2148012&amp;fromtitle=%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2" target="_blank">
       BFS
      </a>
      &nbsp;完成。
     </p>
    </li>
   </ol>
  </div>
 </body>
</html>